W2. Matrix Factorizations

Author

Salman Ahmadi-Asl

Published

January 29, 2026

1. Theory

1.1 Elementary Matrices

Before diving into elementary matrices, recall that an identity matrix is a square matrix with 1’s on the main diagonal and 0’s elsewhere (e.g., ). When we multiply any matrix by the identity, we get back: .

An elementary matrix is a matrix obtained by performing a single elementary row operation on an identity matrix . But what are elementary row operations? These are the three basic operations we can perform on the rows of a matrix:

Swap two rows (interchange)
Multiply a row by a nonzero scalar (scaling)
Add a multiple of one row to another row (row addition)

These operations are fundamental to Gaussian elimination, the systematic method for solving systems of linear equations by transforming a matrix to row echelon form (upper triangular form). Elementary matrices are powerful because they allow us to express these row operations as matrix multiplications: every step of row reduction can be expressed as multiplication by an elementary matrix.

Why does this matter? By representing row operations as matrices, we can track all the steps of Gaussian elimination algebraically. This leads directly to matrix factorizations like LU decomposition, which we’ll study later.

There are three types of elementary matrices, corresponding to the three row operations:

Row Swap : swaps rows and of the identity matrix. Multiplying swaps rows and of .
Row Scaling : multiplies row of the identity by a nonzero scalar . Multiplying scales row of by .
Row Addition : adds times row to row in the identity. Multiplying adds times row to row of .

1.1.1 Inverses of Elementary Matrices

Each elementary matrix is invertible, and its inverse is another elementary matrix that “undoes” the operation:

(swapping twice returns to original)
(scale by to undo)
(subtract what was added)

1.1.2 Determinants of Elementary Matrices

(row swap flips sign)
(adding a multiple of one row to another does not change the determinant)

1.1.3 Fundamental Theorem

Every invertible matrix can be expressed as a product of elementary matrices: The inverse is then:

This is the theoretical basis of Gauss-Jordan elimination: reducing to amounts to left-multiplying by a sequence of elementary matrices.

1.2 Right Multiplication by Elementary Matrices

A crucial distinction: when an elementary matrix multiplies from the left (), it performs a row operation. When it multiplies from the right (), it performs the corresponding column operation.

Operation	Left Multiply	Right Multiply
Row swap	Swaps rows and	Swaps columns and
Row scale	Scales row by	Scales column by
Row add	Adds row to row	Adds col to col
Effect on	Row space	Column space
Preserves	Column relations	Row relations
Use case	Solving	Solving

For example, if and , then swaps rows 2 and 3, while swaps columns 2 and 3.

1.2.1 Properties of Permutation Matrices

A permutation matrix is both symmetric and orthogonal: This means is its own inverse and its own transpose.

For symmetric matrices, we often use symmetric permutations of the form , which simultaneously permute both rows and columns. This preserves symmetry and eigenvalue structure because .

1.3 Triangular Systems

Before discussing why we decompose matrices, we need to understand what makes triangular systems special. A matrix is upper triangular if all entries below the main diagonal are zero (e.g., ). A matrix is lower triangular if all entries above the main diagonal are zero (e.g., ).

Why are triangular systems important? When solving a system of equations , if is triangular, we can solve it extremely efficiently using simple substitution. This is much faster than general methods. The efficiency of triangular systems motivates us to decompose arbitrary matrices into triangular factors — if we can write where is lower triangular and is upper triangular, then solving becomes solving two easy triangular systems instead of one hard general system.

1.3.1 Forward Substitution (Lower Triangular)

For a lower triangular system , we solve from top to bottom because the first equation involves only , the second equation involves only and , and so on. This is called forward substitution.

Example: For :

First:
Second:
Third:

The general formula is:

Or more compactly:

1.3.2 Back Substitution (Upper Triangular)

For an upper triangular system , we solve from bottom to top because the last equation involves only , the second-to-last involves only and , and so on. This is called back substitution.

Example: For :

Last:
Second:
First:

The general formula is:

Or more compactly:

1.4 LU Decomposition

LU decomposition (also called LU factorization) is one of the most important matrix factorizations in linear algebra. It expresses a matrix as the product of a lower triangular matrix and an upper triangular matrix :

The big idea: Instead of solving directly using Gaussian elimination (which requires operations), we can factor once, and then solve any system by solving two triangular systems:

First solve (forward substitution, fast)
Then solve (back substitution, fast)

Since , we have , and setting gives us the two-step process above.

Connection to Gaussian elimination: The matrix is exactly what you get when you perform Gaussian elimination on (the row echelon form). The matrix stores the multipliers used during elimination. A multiplier is the number you use when performing row operations. For example, if you compute “Row 2 - 4×Row 1”, then 4 is the multiplier, and we store it as in .

To ensure uniqueness, we require to be unit lower triangular, meaning has 1’s on its diagonal.

1.4.1 Deriving LU from Gaussian Elimination

During Gaussian elimination, each row operation corresponds to an elementary matrix. If we reduce to using operations , then:

The product is lower triangular. A key convenience: the entries below the diagonal of are simply the negatives of the multipliers used in elimination. For instance, if the operation “subtract 4 times row 1 from row 2” is performed, then (the positive multiplier).

1.4.2 Existence and Uniqueness

An invertible matrix has an LU decomposition (without pivoting) if and only if all its leading principal minors are nonzero.

What’s a leading principal minor? The -th leading principal minor is the determinant of the top-left submatrix of . For a matrix:

(just the top-left entry)
(top-left block)
(the full matrix)

Why does this matter? Each leading principal minor corresponds to a pivot during Gaussian elimination. If , the pivot at position will be zero, and standard LU decomposition fails. In this case, we need pivoting (row swaps).

If is invertible and all leading principal minors are nonzero, then the unit lower triangular LU decomposition is unique. This means there’s exactly one way to write with having 1’s on its diagonal.

Example of failure: The matrix is invertible but , so standard LU decomposition does not exist — pivoting is required.

1.4.3 Why LU is Efficient

If we need to solve for many different right-hand sides , naive Gaussian elimination costs flops. With LU decomposition, we factor once () and then solve each system with forward and back substitution ( each), giving a total cost of . For large , the savings are enormous.

Example: For and right-hand sides, LU requires about 2.67 billion flops vs. 667 billion for repeated Gaussian elimination.

1.5 Pivoting

When performing Gaussian elimination, we work our way down the diagonal, using each diagonal element (called a pivot) to eliminate entries below it. But what happens if a pivot is zero? We can’t divide by zero! Even if a pivot is very small (close to zero), dividing by it can cause huge numerical errors due to round-off in computer arithmetic.

The solution: pivoting. We swap rows (and possibly columns) to place a better (larger in absolute value) element in the pivot position. This process is called pivoting, and it’s essential for both theoretical correctness and numerical stability.

What is numerical stability? In theory, we can work with exact arithmetic. In practice, computers use floating-point numbers with limited precision. Small errors can accumulate and grow. A numerically stable algorithm is one that doesn’t let these errors blow up. Pivoting helps ensure stability by avoiding division by small numbers.

1.5.1 Partial Pivoting

Partial pivoting searches the current column below the diagonal for the largest element in absolute value, then swaps it into the pivot position.

Algorithm at step :

Find such that
Swap rows and
Continue elimination

The result is the factorization: where is a permutation matrix recording all row swaps, is unit lower triangular with , and is upper triangular.

Partial pivoting always exists for any invertible matrix . Once is fixed, and are unique.

1.5.2 Complete Pivoting

Complete pivoting searches the entire remaining submatrix (not just one column) for the largest element:

Algorithm at step :

Find such that
Swap rows and (using )
Swap columns and (using )
Continue elimination

The result is: where permutes rows, permutes columns, is unit lower triangular, and is upper triangular. This factorization exists for any matrix , even singular ones.

1.5.3 Numerical Stability

The growth factor measures how much entries grow during elimination:

No pivoting: can reach (catastrophic)
Partial pivoting: (worst case), but in practice is small
Complete pivoting:

	Partial	Complete
Operation	Row swaps	Row + column swaps
Search cost	per step	per step
Total extra cost
Stability	Usually sufficient	Best possible
Growth bound
Form
Usage	Default in practice	Ill-conditioned/rank-deficient

1.5.4 Rook Pivoting

Rook pivoting is a compromise between partial and complete pivoting: it searches both the current row and column but stops at the first element that is largest in both its row and column. It is almost as stable as complete pivoting with expected cost .

1.5.5 Solving Systems with Complete Pivoting

To solve when complete pivoting is needed:

Compute
Rewrite:
Let , then solve (forward substitution), then (back substitution)
Recover (reverse column permutation)

1.5.6 Determinant with Pivoting

For a permutation matrix :

(row swap)
(column swap)
(simultaneous row and column swap)

In the decomposition :

1.5.7 When to Use Which

Partial pivoting suffices for:

Most well-conditioned problems
Diagonally dominant matrices
Symmetric positive definite matrices (no pivoting needed at all)

Complete pivoting is needed for:

Ill-conditioned matrices (): A matrix is ill-conditioned if small changes in the input can cause large changes in the output. The condition number measures this sensitivity. Large means the problem is difficult numerically.
Rank-deficient matrices: Matrices where some rows/columns are linearly dependent (not full rank), used when determining the rank
Computing the null space: Finding all vectors such that
When backward stability is critical: Applications requiring maximum possible accuracy

1.6 LDU Decomposition

The LU decomposition can be refined further. From , we can factor out the diagonal of to get: where:

is a diagonal matrix containing the pivots from
is unit upper triangular (upper triangular with 1’s on the diagonal)

Why do this? Separating the diagonal pivots into makes the structure clearer. It also reveals special patterns for symmetric matrices (see next section).

1.6.1 Symmetric Case:

If is symmetric (), then in the LDU decomposition, . This gives: This is more storage-efficient (only and are needed) and preserves the symmetry of the matrix.

1.7 Symmetric Positive Definite Matrices and Cholesky Decomposition

A matrix is symmetric if (it equals its transpose, meaning ). Symmetric matrices have special properties and arise frequently in applications (physics, optimization, statistics).

A symmetric matrix is symmetric positive definite (SPD) if for every nonzero vector .

What does this mean intuitively? The expression is called a quadratic form. For SPD matrices, this quadratic form always gives positive values (except at ). Geometrically, this means the matrix defines a “bowl-shaped” surface with no saddle points. SPD matrices are like “well-behaved” matrices — they’re always invertible, have positive eigenvalues, and numerical methods work reliably on them.

1.7.1 Sylvester’s Criterion

Sylvester’s Criterion provides a practical test for positive definiteness: a symmetric matrix is positive definite if and only if all its leading principal minors are positive: , , , .

This is incredibly useful because checking the definition ( for all nonzero ) would require testing infinitely many vectors! Sylvester’s criterion reduces this to computing determinants.

1.7.2 Cholesky Decomposition

For SPD matrices, the decomposition can be taken one step further. Since all diagonal entries of are positive (because all pivots of an SPD matrix are positive), we can write each diagonal entry as a square: . This means where is the diagonal matrix with on the diagonal.

We can then absorb these square roots into and :

If we define , we get:

We typically just write this as (dropping the tilde), where is lower triangular with positive diagonal entries. This is the Cholesky decomposition (or Cholesky factorization).

Advantages of Cholesky:

Costs only flops (half of LU)
Numerically stable without pivoting
Requires only storing one triangular factor

1.8 Matrix Inversion

The inverse of a matrix (denoted ) is the matrix that “undoes” : . Not all matrices have inverses — only invertible (or nonsingular) matrices do. A matrix is invertible if and only if its determinant is nonzero.

Why do we care about inverses? If is invertible, we can solve by computing . However, in practice, we rarely compute explicitly because it’s expensive and numerically unstable. Instead, we use LU decomposition or other factorizations.

1.8.1 The 2x2 Inverse Formula

For a matrix with :

Memory trick: Swap the diagonal entries (), negate the off-diagonal entries, and divide by the determinant.

1.8.2 Gauss-Jordan Method

To find for larger matrices, we use Gauss-Jordan elimination: augment with the identity matrix to form , then apply row operations until the left side becomes . The right side then equals .

Why does this work? The row operations correspond to multiplying by elementary matrices. If we reduce to using operations , then:

This means . Applying the same operations to gives:

So computes the inverse by tracking what operations we apply.

1.8.3 Properties Preserved by Inversion

If is invertible, then :

Is triangular if is triangular (upper stays upper, lower stays lower) — provable by induction
Is symmetric if is symmetric — because
Is NOT necessarily tridiagonal even if is tridiagonal — the inverse is generally a full/dense matrix
Does NOT necessarily have integer entries even if does — the inverse involves division by the determinant

1.9 Matrix Multiplication and Row/Column Interpretation

Matrix multiplication can be understood in several ways. Beyond the standard “dot product of row and column ” definition, there’s a powerful interpretation using linear combinations.

Row perspective: Each row of the product is a linear combination of the rows of , with coefficients from the corresponding row of .

Why? When you compute , you’re taking the -th row of and the -th column of . But if you look at the entire -th row of , it’s:

Column perspective: Each column of is a linear combination of the columns of , with coefficients from the corresponding column of :

Example: If and , then the first row of is:

This perspective is crucial for understanding how elementary matrices work: left multiplication affects rows, right multiplication affects columns.

2. Definitions

Elementary Matrix: A matrix obtained by performing a single elementary row operation on the identity matrix.
Row Swap Matrix (): An elementary matrix that swaps rows and ; also called a permutation matrix.
Row Scaling Matrix (): An elementary matrix that multiplies row by a nonzero scalar .
Row Addition Matrix (): An elementary matrix that adds times row to row .
LU Decomposition: A factorization where is unit lower triangular and is upper triangular.
Leading Principal Minor (): The determinant of the top-left submatrix of a matrix.
Partial Pivoting: A pivoting strategy that swaps rows to place the largest element (in absolute value) in the current column into the pivot position, yielding .
Complete Pivoting: A pivoting strategy that swaps both rows and columns to place the largest element in the remaining submatrix into the pivot position, yielding .
Rook Pivoting: A compromise pivoting strategy that searches both the current row and column for the first element that is largest in both.
Growth Factor (): The ratio of the largest entry appearing during elimination to the largest entry of the original matrix; measures numerical stability.
LDU Decomposition: A factorization where is unit lower triangular, is diagonal (containing the pivots), and is unit upper triangular.
Symmetric Positive Definite (SPD) Matrix: A symmetric matrix such that for every nonzero vector .
Sylvester’s Criterion: A symmetric matrix is positive definite if and only if all its leading principal minors are positive.
Cholesky Decomposition: For SPD matrices, where is lower triangular with positive diagonal entries.
Matrix Equivalence: Two matrices and are equivalent if there exist invertible matrices and such that .
Gauss-Jordan Elimination: A method to compute by row-reducing the augmented matrix to .

3. Formulas

Inverse of Row Swap:
Inverse of Row Scaling:
Inverse of Row Addition:
Determinant of Row Swap:
Determinant of Row Scaling:
Determinant of Row Addition:
LU Decomposition: (exists when all leading principal minors )
LU with Partial Pivoting: (exists for any invertible )
LU with Complete Pivoting: (exists for any matrix , including singular)
LDU Decomposition: where and
Symmetric LDU: (when is symmetric)
Cholesky Decomposition: (when is symmetric positive definite)
Cholesky Cost: flops
LU Cost: flops for factorization, flops per solve
Forward Substitution:
Back Substitution:
Determinant from PAQ = LU:
2x2 Inverse:
Transpose of Inverse:
Invertible Matrix as Product of Elementary Matrices:

4.9. Solving Systems with Given LU Factorization (Part 3) (Assignment 2, Task 3)

Solve the equation by using the LU factorization given for :

Click to see the solution

Solution:

Step 1. Solve by forward substitution.

Step 2. Solve by backward substitution.

Answer:

4.10. Solving Systems with Given LU Factorization (Part 4) (Assignment 2, Task 4)

Solve the equation by using the LU factorization given for :

Click to see the solution

Solution:

Step 1. Solve by forward substitution.

Step 2. Solve by backward substitution.

Answer:

4.11. Solving Systems with Given LU Factorization (Part 5) (Assignment 2, Task 5)

Solve the equation by using the LU factorization given for :

Click to see the solution

Solution:

Step 1. Solve by forward substitution.

Step 2. Solve by backward substitution.

Answer:

4.12. Matrix Multiplication and Row Interpretation (Tutorial 2, Task 1)

Matrix multiplication can be interpreted through linear combinations. Show how each row of the product is a linear combination of rows of .

Click to see the solution

Solution:

Step 1. Compute .

Step 2. Express the first row as a linear combination of rows of .

Step 3. Express the second row as a linear combination of rows of .

Answer: Each row of is a linear combination of the rows of with coefficients from the corresponding row of .

4.13. Effect of Elementary Matrices on Rows and Columns (Tutorial 2, Task 2)

Describe the rows of and the columns of if

Click to see the solution

Solution:

Rows of :

When multiplies from the left, it performs row operations on .

1st row of
2nd row of

This is a row addition operation: row 1 gets row 1 plus 7 times row 2.

Columns of :

When multiplies from the right, it performs column operations on .

1st column of
2nd column of

This is a column addition operation: column 2 gets 7 times column 1 plus column 2.

Answer: Left multiplication by affects rows (row 1 becomes row 1 + 7·row 2). Right multiplication by affects columns (column 2 becomes 7·column 1 + column 2).

4.14. Elementary Matrices and Matrix Products (Tutorial 2, Task 3)

Write down the 3 by 3 matrices that produce these elimination steps: a) subtracts 5 times row 1 from row 2. b) subtracts -7 times row 2 from row 3.

Then compute: (i) and (ii) for .

Click to see the solution

Solution:

Step 1. Write the elementary matrices.

Step 2. Compute .

Step 3. Compute .

Answer:

(row 3 feels effect of row 1)
(row 3 feels no effect from row 1)

4.15. LU Decomposition by Elimination (Part a) (Tutorial 2, Task 4a)

Apply elimination to produce the factors and for:

Click to see the solution

Solution:

Step 1. Perform Gaussian elimination to get .

Step 2. Find the elementary matrix and its inverse .

Answer: and

4.16. LU Decomposition by Elimination (Part b) (Tutorial 2, Task 4b)

Apply elimination to produce the factors and for:

Click to see the solution

Solution:

Step 1. Perform Gaussian elimination to get .

Step 2. Find from the inverse of elementary matrices.

Answer: and

4.17. Conditions for Matrix to be Nonsingular (Tutorial 2, Task 5a)

Under what conditions is the following product nonsingular?

Click to see the solution

Solution:

Step 1. Identify the matrix structure.

We have where:

(lower triangular with 1’s on diagonal)
(diagonal)
(upper triangular with 1’s on diagonal)

Step 2. Apply the determinant property.

Since and , :

Step 3. Determine nonsingularity condition.

Matrix is nonsingular if and only if , which requires:

Answer: is nonsingular if and only if all diagonal entries are nonzero: , , .

4.18. Solving System with LDU Decomposition (Tutorial 2, Task 5b)

Solve the system starting with :

where the full decomposition is .

Click to see the solution

Solution:

Step 1. Solve for by forward substitution.

Step 2. Now we need to solve .

This gives:

Step 3. Solve by back substitution.

Answer: (assuming )

4.19. Find L and D from Upper Triangular Matrix (Tutorial 2, Task 6)

What are and for this matrix ? What is in ?

Click to see the solution

Solution:

Step 1. Identify the structure of .

Since is already upper triangular with nonzero diagonal entries (2, 3, 7), we have:

The pivots are the diagonal entries
No elimination is needed

Step 2. Extract , , and from .

Step 3. Find in .

For the decomposition (without diagonal factorization):

Answer: , , ,

4.20. Relationship Between Matrix Inverses (Tutorial 2, Task 7)

If the inverse of is , show that the inverse of is .

Click to see the solution

Solution:

Step 1. Start with the given condition.

Given:

This means:

Step 2. Show that is the inverse of .

We want to show that .

Starting from :

Since , the equation can be factored directly:

This shows that is a right inverse of .

Step 3. Verify it’s also a left inverse.

From , we can write:

By properties of invertible matrices, if a right inverse exists and is square, it must also be a left inverse.

Answer: Since , we have , which means . Thus, the inverse of is .

4.21. Properties Preserved by Matrix Inversion (Tutorial 2, Task 8)

If is invertible, which of the following properties are preserved in ?

is triangular → is triangular ✓
is symmetric → is symmetric ✓
is tridiagonal → is tridiagonal ✗
All entries are whole numbers → has whole numbers ✗
All entries are fractions → has fractions ✓

Click to see the solution

Solution:

Property (a): Triangular matrices

If is upper triangular, we can write where is upper triangular.

By the block matrix inverse formula:

By induction, is upper triangular, so is upper triangular. ✓

Property (b): Symmetric matrices

If , then:

So is symmetric. ✓

Property (c): Tridiagonal matrices

Counterexample:

Computing yields:

This is not tridiagonal. ✗

Property (d): Integer entries

Counterexample:

has all integer entries, but has fractional/decimal entries. ✗

Property (e): Fractional entries

If all entries of are fractions, then where has integer entries and is a common denominator.

The inverse still involves only division, resulting in fractional entries. ✓

Answer: Properties (a), (b), and (e) are preserved. Properties (c) and (d) are NOT preserved.

4.22. Invertibility Conditions for Triangular Matrices (Part a) (Tutorial 2, Task 9a)

Under what conditions on their entries are the following matrices invertible?

Click to see the solution

Solution:

Step 1. Apply Gauss-Jordan elimination to find invertibility conditions.

Step 2. Swap rows to bring to pivot position.

Swap rows 1 and 3:

This requires:

Step 3. Eliminate below first pivot.

and :

This requires:

Step 4. Eliminate in row 3, column 2.

This requires:

Answer: Matrix is invertible if and only if , , and (or equivalently, the three diagonal-like entries are nonzero: , , ).

4.23. Invertibility Conditions for Block Diagonal Matrices (Tutorial 2, Task 9b)

Under what conditions on their entries is the following matrix invertible?

Click to see the solution

Solution:

Step 1. Recognize the block diagonal structure.

where is the upper-left block.

Step 2. Apply the block matrix determinant formula.

Step 3. Determine invertibility condition.

Matrix is invertible if and only if :

This requires both:

(the block is invertible)
(the scalar is nonzero)

Answer: Matrix is invertible if and only if and .

4.24. Compute 2×2 Matrix Inverses (Tutorial 2, Task 10)

Find the inverses (directly or from the 2×2 formula) of:

, ,

Click to see the solution

Solution:

The 2×2 inverse formula:

For matrix A:

For matrix B:

(valid for )

For matrix C:

Answer:

(for )

Find using Gauss-Jordan elimination.

Click to see the solution

Solution:

Step 1. Set up the augmented matrix.

Step 2. Eliminate above the second pivot.

Step 3. Normalize the first row.

Answer:

4.29. General Pattern for Elementary Lower Triangular Matrices (Part a) (Tutorial 2, Task 13a)

By experiment or Gauss-Jordan method, find .

Click to see the solution

Solution:

Step 1. Compute the matrix squared.

Step 2. Compute the matrix cubed.

Step 3. Identify the general pattern.

Answer:

4.30. Inverse of Elementary Lower Triangular Matrix (Part b) (Tutorial 2, Task 13b)

Find .

Click to see the solution

Solution:

Step 1. Use the pattern from Part a with .

From the pattern

Setting :

Step 2. Verify by multiplication.

✓

Answer:

4.31. Inverse of Modified Lower Triangular Matrix (Part c) (Tutorial 2, Task 13c)

Find using Gauss-Jordan elimination.

Click to see the solution

Solution:

Step 1. Set up the augmented matrix .

Step 2. Eliminate below the first pivot.

Step 3. Eliminate below the second pivot.

Answer: